// https://leetcode.cn/problems/add-two-numbers/description/

// 算法思路总结：
// 1. 使用虚拟头节点简化链表操作
// 2. 同时遍历两个链表，逐位相加并处理进位
// 3. 考虑链表长度不同和最后进位的情况
// 4. 时间复杂度：O(max(m,n))，空间复杂度：O(max(m,n))

#include <iostream>
using namespace std;

#include <vector>

struct ListNode
{
    int _val;
    ListNode* _next;
    ListNode() : _val(0), _next(nullptr) {}
    ListNode(int val) : _val(val), _next(nullptr) {}
    ListNode(int val, ListNode* next) : _val(val), _next(next) {}
};

ListNode* createLinkedList(const vector<int>& nums)
{
    if (nums.empty()) return nullptr;
    
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    
    for (int num : nums)
    {
        cur->_next = new ListNode(num);
        cur = cur->_next;
    }
    
    ListNode* head = dummy->_next;
    delete dummy;
    return head;
}

void printLinkedList(ListNode* head)
{
    if (!head)
    {
        cout << "空链表" << endl;
        return;
    }
    
    ListNode* cur = head;
    while (cur)
    {
        cout << cur->_val;
        if (cur->_next)
            cout << " -> ";
        else
            cout << " -> nullptr";
        cur = cur->_next;
    }
    cout << endl;
}

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        int carry = 0;

        while (l1 || l2 || carry)
        {
            int digit = carry;
            if (l1)
            {
                digit += l1->_val;
                l1 = l1->_next;
            }
            if (l2)
            {
                digit += l2->_val;
                l2 = l2->_next;
            }

            carry = digit / 10;
            cur->_next = new ListNode(digit % 10);
            cur = cur->_next;
        }
        return dummy->_next;
    }
};

int main()
{
    vector<int> v11 = {2,4,3}, v12 = {5,6,4};
    vector<int> v21 = {9,9,9,9,9,9,9}, v22 = {9,9,9,9};
    Solution sol;

    auto l11 = createLinkedList(v11), l12 = createLinkedList(v12);
    auto l21 = createLinkedList(v21), l22 = createLinkedList(v22);
    auto r1 = sol.addTwoNumbers(l11, l12);
    auto r2 = sol.addTwoNumbers(l21, l22);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}